// 1,4,9,16,25,36...100
var cp [101]int

func init() {
	for i := 1; i < 101; i++ {
		cp[i] = i * i
	}
}

func numSquares(n int) int {
    dp := make([]int, n + 1)	
	dp[1] = 1
	for i := 2; i < n + 1; i++ {
		dp[i] = dp[i - 1] + 1
		for j := 2; j < 101; j++ {
			if i >= cp[j] {
				dp[i] = min(dp[i], dp[i - cp[j]] + 1)
			}
			
		}
	} 
	return dp[n]
}